package Z.dailyExercise._0222;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 约瑟夫问题
 */
public class _剑指Offer62圆圈中最后剩下的数字 {

    //最优解释--数组 见pad
    public int lastRemaining2(int n, int m) {
        int f = 0;//表示n=1时 序号结果
        for (int i=2;i<=n;i++){//从n=2开始递推
            f = (f+m)%i;//m表示当前右移 取余时多余的前移
        }
        return f;
    }
    /**
     * 构建一个队列：先把所有的数字都push进去  pop一个 计数 判断是不是m的倍数  如果不是push回去 直到队列只有一个数子 返回
     *
     * 超出时间限制
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining(int n, int m) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0;i<n;i++){
            queue.add(i);
        }
        int count=0,temp=0;
        while (queue.size()>1){
            temp = queue.poll();
            count++;
            if (count%3!=0){
                queue.add(temp);
            }

        }

        return queue.poll();
    }


    /**
     * 约瑟夫学习--借助单项循环连标
     * 也超时了
     */
    public int lastRemaining1(int n, int m) {
        circleLinkedList linkedList = new circleLinkedList();
        linkedList.addNode(n);

        Node helper = linkedList.first;
        int count =1;
        while ( helper.getNext() != helper){
            count++;
            if (count % m == 0){
                helper = helper.getNext().getNext();
            }else {
                helper = helper.getNext();
            }

        }

        return helper.getVal();
    }


}

//结点类
class Node{
    private int val;
    private Node next;

    public Node(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

//构建循环联biao
class circleLinkedList{

    //
    //构建第一个头节点
    Node first = new Node(-1);


    //用来增加结点 参数表示结点的val
    public void addNode(int num){
        Node last = null;//永远指向已形成链表的最后一个结点

        for (int i=1;i<=num;i++){
            Node cur = new Node(i);//临时结点
            //第一个结点特殊处理
            if (i==1){
                first = cur;
                last = first;
                last.setNext(first);
            }else {
                last.setNext(cur);
                last = cur;
                last.setNext(first);
            }
        }

    }

    //遍历 利用first就可以判断当前表里还有没有结点

}